#include <bits/stdc++.h>

using namespace std;

class ListNode
{
public:
    int val;
    ListNode *next;
    ListNode(int val)
    {
        this->val = val;
        this->next = NULL;
    }
};

void printListNode(ListNode * head){
    if(head == NULL)
        printf("NULL");
    while(head != NULL){
        printf("%d\t", head->val);
        head = head->next;
    }
    printf("\n");
}

ListNode * reverseBetween(ListNode * head, int m, int n)
{
    // write your code here
    if(head == NULL || head->next == NULL || m == n)
        return head;
    ListNode * phead = head, * first, * last, *prehead = NULL;
    for(int i = 1; phead!= NULL; i++){
        if(i == m)
            first = prehead;
        if(i == n)
            last = phead->next;
        prehead = phead;
        phead = phead->next;
    }
    ListNode * overhead, * temphead;
    if(first == NULL){
        overhead = new ListNode(head->val);
        phead = head->next;
    }
    else{
        overhead = new ListNode(first->next->val);
        phead = first->next->next;
    }
    overhead->next = last;
    while(phead != last){
        temphead = new ListNode(phead->val);
        phead = phead->next;
        temphead->next = overhead;
        overhead = temphead;
    }
    if(first == NULL)
        return overhead;
    first->next = overhead;
    return head;
}

int main()
{
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    printListNode(head);
    printListNode(reverseBetween(head, 2, 4));
    printListNode(reverseBetween(head, 1, 5));
    printListNode(reverseBetween(head, 1, 2));
    printListNode(reverseBetween(head, 4, 5));
    printListNode(reverseBetween(head, 4, 4));
    return 0;
}
